package com.longge;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-04-24 18:15
 */
public class UF1 {

    private Map<Integer, Integer> parentMap;

    private int count;

    private Map<Integer,Integer> sizeMap;


    public UF1() {
        this.parentMap = new HashMap<>();
        this.sizeMap = new HashMap<>();
        this.count = 0;
    }

    public Boolean connected(int p, int q) {
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        return rootP == rootQ;
    }

    public int findRoot(int x) {
        if (!parentMap.containsKey(x)) {
            parentMap.put(x, x);
            sizeMap.put(x,1);
            count++;
        }
        if (x!=parentMap.get(x)){
            parentMap.put(x,findRoot(parentMap.get(x)));
        }
        return parentMap.get(x);
    }

    public void union(int p, int q) {
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        if (rootP == rootQ) return;
        Integer pSize = sizeMap.get(rootP);
        Integer qSize = sizeMap.get(rootQ);
        if (pSize>qSize){
            parentMap.put(rootQ,rootP);
            pSize+=qSize;
            sizeMap.put(rootP,pSize);
        }else {
            parentMap.put(rootP,rootQ);
            qSize+=pSize;
            sizeMap.put(rootQ,qSize);
        }
        count--;
    }

    public int count() {
        return count;
    }


}
